Known schemes for computer processing a given pictorial image into a more amendable form typically depends on recognizing the boundaries or contours of important objects in the image, since boundaries of objects are usually an important intermediate representation in going from initial intensity data to final interpretation of the image. Object boundaries are often identified by significant changes in intensity over some small neighborhood and so edge detection attempts to identify pixels in the image where there is a large intensity gradient. However, edge detectors do not group individual edge elements (edgels) together to form contours. This is left to a further level of processing.
Associating edge points with a contour is difficult because the input data is noisy, there may be false and/or missing measurements, there are ambiguities because, for example, in an image contours may intersect and interfere with one another, the number of perceptually relevant groupings is unknown before hand and may change with time, some groups unexpectedly terminating and others being created. The correspondence problem (or data association problem) is what makes perception different from traditional estimation and control problems. The fundamental problem is that we have both uncertainty in the origins of measurements as well as in the values of the measurements.
The Hough transform is probably the most popular algorithm for detecting lines. However, it does not explicitly indicate the start and end points of the line segment. Moreover, choosing the size of the accumulator array can be problematic. Most importantly, the Hough transform is only appropriate when the general shape of the contour, e.g. straight line, circle etc., is known. It is not appropriate for linking edgels to form arbitrary contours.
Edge following as graph search has some similarities to the algorithm proposed hereinafter, particularly in its need to search trees. However, measurement noise, e.g. errors in the location of edgels, is not explicitly modeled, nor is there any attempt to estimate the likelihood of a particular contour given the measurement and data association uncertainties.